// 题目描述：给定一个没有重复数字的序列，返回其所有可能的全排列。
/**
 * 示例：   
输入: [1,2,3]
输出: [
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
 */
/**
 * 思路分析：
 * 从n个不同元素中任取m（m≤n）个元素，按照一定的顺序排列起来，叫做从n个不同元素中取出m个元素的一个排列。
 * 当m=n时所有的排列情况叫全排列。
 * 拿到一个 n 个数的数组作为入参，穷举出这 n 个数的所有排列方式。    
 * 这里给大家一个思维工具：以后只要分析出重复的逻辑（排除掉类似数组遍历这种简单粗暴的重复），
 * 你都需要把递归从你的大脑内存里调度出来、将其列为“可以一试”的解法之一；只要想到递归，立刻回忆我们上一节讲的 DFS 思想、
 * 然后尝试套我们这一节末尾教给大家的解题模板。
 * 这个脑回路未必 100% 准确，但确实有极高的成功概率——题，是有规律的。这，就是规律之一。 
 * 
 * 在以上的“填坑”过程中，我们重复地做了以下事情：
 * 1. 检查手里剩下的数字有哪些
 * 2. 选取其中一个填进当前的坑里   
 * 
 * 比如说示例中有 n  个坑，假如我们把第 1 个坑的索引记为 0 ，那么索引为 n-1   的坑就是递归式的执行终点，
 * 索引为 n  的坑（压根不存在）就是递归边界。 

 * 递归的编码实现，无非是把我们递归式和递归边界翻译成代码
 */

// 入参是一个数组
const permute = function(nums) {
	// 缓存数组的长度
	const len = nums.length;
	// curr 变量用来记录当前的排列内容
	const curr = [];
	// res 用来记录所有的排列顺序
	const res = [];
	// visited 用来避免重复使用同一个数字
	const visited = {};
	// 定义 dfs 函数，入参是坑位的索引（从 0 计数）
	function dfs(nth) {
		// 若遍历到了不存在的坑位（第 len+1 个），则触碰递归边界返回
		if (nth === len) {
			// 此时前 len 个坑位已经填满，将对应的排列记录下来
			res.push(curr.slice());
			return;
		}
		// 检查手里剩下的数字有哪些
		for (let i = 0; i < len; i++) {
			// 若 nums[i] 之前没被其它坑位用过，则可以理解为“这个数字剩下了”
			if (!visited[nums[i]]) {
				// 给 nums[i] 打个“已用过”的标
				visited[nums[i]] = 1;
				// 将nums[i]推入当前排列
				curr.push(nums[i]);
				// 基于这个排列继续往下一个坑走去
				dfs(nth + 1);
				// nums[i]让出当前坑位
				curr.pop();
				// 下掉“已用过”标识
				visited[nums[i]] = 0;
			}
		}
	}
	// 从索引为 0 的坑位（也就是第一个坑位）开始 dfs
	dfs(0);
	return res;
};

const arr = [1,2,3]
console.log(permute(arr));
